package Algorithms;

/**
 * A*算法类
 * @author 车宗绍Che Zongshao
 * @date 2015/1/7
 */

import utils.BinaryHeap;
import utils.Graph;
import utils.Node;

public class AStar {
	
	private Graph graph;
	private static BinaryHeap binHeap;
	
	/**
	 * 执行A*算法
	 */
	public static Node[] doAStar() {
		binHeap = new BinaryHeap();
		
		// TODO 把root加入最小堆中
		Node root = Graph.getRoot();
		Node target = Graph.getTarget();
		root.setBitmap((byte) 0x1);		// 从A开始
		root.setGn(0);
		root.setFn(fn(root, root));
		binHeap.insert(root);
		
		Node tmp_father = null;
		while (!binHeap.isEmpty()) {
			// TODO 取出最小堆中第一个节点,如果是最后一个节点,则找到解
			tmp_father = binHeap.deleteMin();
			if (tmp_father == null) {
				// 无解
				break;
			}
			if (tmp_father.getName() == target.getName()) {
				// 找到解
				break;
			}
			// TODO 扩展节点
			for (int i = 0; i < tmp_father.getNextEdges().length; i++) {
				int sonName = 0;
				int position = tmp_father.getPosition();
				if (position < Graph.getNodes().length) {
					// 在其他节点中寻找子节点
					if (tmp_father.getNextEdges()[i].getEnd().getName() != target.getName()) {
						sonName = tmp_father.getNextEdges()[i].getEnd().getName();
					} else {
						continue;
					}
				} else {
					// 必须指向终点E
					sonName = target.getName();
				} 
				if (!tmp_father.isEdgeUsed(sonName)) {
					// 子节点未在路径中出现过
					Node tmp_son = new Node(tmp_father, sonName);
					tmp_son.setGn(gn(tmp_father, tmp_son));
					tmp_son.setFn(fn(tmp_father, tmp_son));
					binHeap.insert(tmp_son);
				}
			}
		}
		
		// TODO 处理结果
		if (tmp_father.getName() == target.getName()) {
			Node[] result = new Node[Graph.getNodes().length+1];
			for (int i = Graph.getNodes().length; i >=0; i--) {
				result[i] = tmp_father;
				tmp_father = tmp_father.getFather();
			}
			return result;
		}
		return null;
	}

	/**
	 * 计算f(n) = g(n) + h(n)
	 * @param father
	 * @param son
	 * @return
	 */
	public static double fn(Node father, Node son) {
		return gn(father, son) + hn(son);
	}
	
	/**
	 * 计算g(n)=路程长度
	 * @param father
	 * @param son
	 * @return
	 */
	public static double gn(Node father, Node son) {
		if (father.getName() == son.getName()) {
			return father.getGn();
		}
		return father.getGn() + father.getEdge(son.getName()).getLength();
	}
	
	/**
	 * 计算h(n)=子节点最短未使用邻接边长度
	 * @param father
	 * @param son
	 * @return
	 */
	public static double hn(Node son) {
		if (son.getName() == 5) {
			// E
			return 0;
		}
		int min = 10000;
		for (int i = 0; i < son.getNextEdges().length; i++) {
			Node end = son.getNextEdges()[i].getEnd();
			if (!(son.isEdgeUsed(end.getName())) && 
					son.getNextEdges()[i].getLength() < min) {
				min = son.getNextEdges()[i].getLength();
			}
		}
		return min;
	}

	public Graph getGraph() {
		return graph;
	}

	public void setGraph(Graph graph) {
		this.graph = graph;
	}

	public static BinaryHeap getBinHeap() {
		return binHeap;
	}
}